Shareware Grab Bag

home *** CD-ROM | disk | FTP | other *** search

/ Shareware Grab Bag / Shareware Grab Bag.iso / 014 / qsort300.arc / QSORT.DOC < prev next >

Wrap

Text File | 1987-03-12 | 25.0 KB | 524 lines

QSORT - Version 3.00 Copyright (c) 1985, 1986, 1987 - Ben Baker - All rights reserved QSORT may be freely copied and distributed. provided that 1) it is distributed under the name "QSORT," and 2) this documentation file always accompanies it. Vendors wishing to distribute QSORT commercially, or with commercial products may contact the author at the address below for terms. QSORT is made available under the "share-ware" concept. If you find this program useful, you are asked to send its author a license fee of $20 for each machine on which you use it. This will encourage the development of other useful, affordable tools. Send checks to: Ben Baker RR #1, Box 637 E. Alton, Il 62024 Bug reports or suggestions may be sent to the above address or via FidoNet mail to Fido node # 100/76, Baker's Acre, or by logging into Baker's Acre BBS at 618-251-2169. --- INTRODUCTION --- QSORT was first designed to be a replacement for, and to overcome the limitations of DOS SORT, but has been enhanced a number of times and moved to new compilers twice. The current version will sort files whose size is limited only by available disk space. File name(s) may be given explicitly or QSORT will sort from standard input to standard output, and so, may be used in pipes or with redirection. Multiple key fields may be specified. Binary files with fixed-length records may be sorted, provided only that keys are ASCII fields. QSORT tries to be very protective of your data. If QSORT has an error of any kind, it will terminate with the input file still intact, and will return to DOS with ERRORLEVEL = 1. When QSORT successfully completes a sort, it terminates with ERRORLEVEL set to 0. (See the batch commands in your DOS manual for more information on ERRORLEVEL.) The command line syntax is a super-set of SORT's, so QSORT may be used without other changes in batch files using SORT, but in most cases you will probably want to make use of QSORT's greater capabilities. --- The QSORT Command and Options --- QSORT is invoked with the following command: QSORT [<in_file> [<out_file>]] [/<key_spec>. . .] [/T[<tag>] | /F<len>] [/R] [/S] [/?] Note that all parameters on the command line are optional. The <in_file> and <out_file> parameters are "ASCII-Z" file specifiers. They may contain disk and path information in the standard DOS format, but must not contain "wild-card" characters. If <in_file> is missing, QSORT sorts from standard input to standard output. These are files defined and opened by DOS before QSORT is loaded. (See your DOS manual concerning the use of redirection and pipes.) If <in_file> is given but <out_file> is missing, QSORT creates a temporary file in the directory containing <in_file> and sorts to the temporary file. On successful completion of the sort, <in_file> is deleted and the temporary is renamed to <in_file>. The effect is an apparent "sort-in-place." If both file names are given, <in_file> is unchanged and the sorted output is written to <out_file>. This feature was added in version 3.00 as a convenience. New DOS users sometimes have difficulty with the concept of redirection. Note that the following two commands are exactly equivalent: QSORT FILE.TXT FILE.SRT QSORT <FILE.TXT >FILE.SRT In the first, QSORT opens the files. In the second, redirection is specified and DOS opens the files. The result is the same. It is an error QSORT can't detect if you mix these. For instance: QSORT FILE.TXT >FILE.SRT will result in a sort-in-place. QSORT will open FILE.TXT but won't know DOS has opened FILE.SRT for it, and will ignore it. The /<key_spec> Parameter Up to 30 /<key_spec> parameters may be used to specify key fields and are ordered major to minor from left to right. The /<key_spec> argument has the form: /[L][+|-][col][:width] Note that all elements of this argument are "optional," but at least one element must be present following the slant-bar (/). The 'L', if present, specifies "lexical" sequence for this field. (See discussion of lexical sequence below.) The minus (-) sign specifies reverse order for this field. The plus (+) sign (or no sign) specifies normal sort order. If present, [col] defines the beginning column of the field. If omitted, column 1 is assumed. If present, [:width] defines the field width in columns. If width is omitted, the rest of the record is assumed to be part of the key. If no key field parameters are given, the entire record is the key field. When sorting variable-length records, any key field which falls beyond the end of a particular record is treated as a null (zero length) field for that record, and collates low. When sorting fixed-length records, all defined fields must fall within the defined record length. The /F<len> Parameter The /F<len> parameter defines the record length for a file of fixed-length records. All records in the input file MUST be exactly <len> bytes long. The records need not (but may) be terminated with a CR/LF sequence. They may contain any data, even binary data, but the key fields must be ASCII strings. Strings may be terminated with a null (binary zero) character, or may be padded with trailing spaces to the full length of the field. Note that QSORT does not attempt to support Pascal style strings. These are strings which begin with a character whose binary value is a character count. This is followed by <count> characters of ASCII data, which in turn is followed by random data out to the maximum length of the string. These strings may be used as key fields, but the programmer must insure that either the last real character is a null character, or the field is padded to its full length with spaces. QSORT must be told that the key begins in the second character position (the first character of real data). The /T[<tag>] Parameter The /T[<tag>] parameter, if present, indicates that the "records" to be sorted may be more than a single line long. If <tag> is also present, it defines a character to be used to tag the "end-of-record." If <tag> is not present, the first empty line terminates the record. For this purpose, "empty" means "no characters." A line containing but a single space is NOT empty! A line may be "tagged" by placing the <tag> character anywhere on the last line of a logical record. The entire line, including the tag character will appear as the last line of the record. Note that the /F<len> and /T[<tag>] parameters are incompatible, and may not both be specified. The /R Parameter The /R parameter is included for compatibility with DOS SORT and is redundant. It reverses the sense of sort direction for all key fields. The /S Parameter The /S parameter tells QSORT to make a statistics report to the screen at the end of a run. The report is written to the "standard error" device, the console, and may not be redirected. The following is an actual statistics report "cut" from the screen after QSORT had sorted a 1 mega-byte+ file: QSORT - Text Sort - Version 3.00 Copyright (c) 1985, 1986, 1987 - Ben Baker - All rights reserved 10131 records sorted 146 bytes in longest record 116744 sort phase comparisons 53771 merge phase comparisons 170515 total comparisons 16.8 comparisons per input record 21 temporary merge files created 2 merge passes 2.3 average passes over data 6:00 elapsed time The first two numbers are self-explanatory. The next two are the number of times two records were compared during the sort phase and the merge phase respectively, followed by the total comparisons. The next number is total comparisons divided by the number of records in the input file. If there is no merge phase, this number is typically 10 to 12. If the file is large enough to require merging, it is 12 to 20, on average. If it is much larger than 20, it usually means that there is something unusual about your input file. It may already be sorted, or there may be large blocks of records which compare equal. This can happen if you sort on, say column 50 and the input file contains a large number of records shorter than 50 bytes. In this case, a minor sort key at column 1 may significantly speed sorting. The next two items are self-explanatory. "Average passes over data" reflects the number of times each record was read and written. For short files not requiring a merge pass, this number will be 1.0. When merging is needed, the last merge pass is the one which writes the output file and it must read and write every record exactly once. Thus when only one merge pass is made, there will be exactly 2.0 "average passes over data." In the above case the first merge pass processed about 30% of the records, hence the value of 2.3. The above sort was performed on an IBM XT with two hard drives (C and D). The input file was on C; the temporary merge files were placed on D; and the output file was written to C. The sort of a 1 mega-byte file took six minutes flat. With my Tiny Turbo accelerator turned on, the same sort takes about 3:50. The /? Parameter The /? parameter requests help or parameter evaluation. When QSORT is executed with the /? parameter alone, it lists a short description of the QSORT parameters. If /? is entered as one of several parameters, QSORT will produce a short report on the screen describing the sort it would perform based on those parameters without actually doing a sort. For example: QSORT /? /L5:12 /-3:2 /22 /T /R <INFILE.TXT >OUTFILE.TXT requests a sort on a file of tagged records. It defines three key fields, one of them inverted (-). The /R parameter reverses the sense of all three fields. Since redirection is specified, QSORT does not see or know about the names of the files it will sort. The /? parameter requests a report, rather than a sort, and QSORT obligingly produces on the screen, the following: QSORT - Text Sort - Version 3.00 Copyright (c) 1985, 1986, 1987 - Ben Baker - All rights reserved With the present arguments, QSORT would sort from STDIN to STDOUT Records are multiple lines ending with an empty line Key fields in descending order of importance are: Pos Len Type 5 12 Lexical Descending 3 2 ASCII 22 65535 ASCII Descending The third field has an unspecified length. The value "65535" merely means that this field extends to the end of each record. The /M<len> supported in earlier versions of QSORT is no longer required, but will be accepted (and ignored) by QSORT. There is no "hard-coded" maximum record length in QSORT, but there is a practical limit. At some time during every sort, the two longest records in the input file must be compared. Therefore, the two longest records must be able to fit together in the sort buffer. The sum of their lengths cannot exceed about 50K -- not an altogether unreasonable limitation. QSORT can be shoe-horned into tighter memory and will run if it can find 4K for a sort buffer and 4K for an output buffer, but the two longest records must still fit in the sort buffer together. Arguments may appear in any order on the command line except that <in_file> must appear before <out_file>, and /<key_spec> arguments must appear in descending order of importance. --- Lexical Sorting --- The lexical sorting capability was borne out of my own need to sort word lists with mixed capitalization. ASCII sequence produced some bizarre results when words beginning with 'Z' sorted before those beginning with 'a.' Case-insensitive sorting wasn't much better because upper and lower case got mixed randomly. The following table will illustrate what I mean: INPUT ASCII CASE LEXICAL INSENSITIVE DeLaPort Baker Baker Baker Smith Brown brown Brown brown DeAngelo bRown bRown deLaPorte DeLaPort Brown brown Deangelo Deangelo Deangelo DeAngelo deAngelo Deangelo deangelo Deangelo Brown DelaPort Deangelo Deangelo smith DelaPorte deAngelo deAngelo delaPorte Harry DeAngelo deangelo DelaPort Smith delaPort DeLaPort DeAngelo bRown DelaPort DelaPort DelaPorte brown delaPort delaPort deangelo deAngelo DeLaPort delaPort Harry deLaPorte DelaPorte DelaPorte delaPort deLaPorte deLaPorte deLaPorte Baker deangelo delaPorte deLaPorte deLaPorte delaPort deLaPorte delaPorte Deangelo delaPort Harry Harry bRown delaPorte smith Smith delaPort smith Smith smith The first column is a list of names in arbitrary order. The second is an ASCII sort of that list. Third we have one possible case-insensitive sort of the list. The fourth column is what I really wanted. It is sorted the way these words would be sorted in a dictionary (or lexicon). The third and fourth columns both collect words of identical spellings together, but in the third column, upper and lower case spellings are in arbitrary order, while the fourth column places upper case spellings ahead of lower case spellings. For example, the two occurrences of Smith are widely separated in column 2 because one is capitalized and the other is not. Column 3 brings the two together, but in the wrong order. They might have been in the right order, but the order is strictly arbitrary. In column 4, Smith comes before smith, and lexical sorting will always put them in this order. Lexical sorting is achieved by making case-insensitive comparisions of entire fields. If the fields compare equal, an ASCII comparison is made to arbitrate ties. In other words, when "lexical" fields in two records have different spellings, the case-insensitive comparison determines the order of the records. When "lexical" fields are spelled the same, the case-sensitive comparison determines the order of the records. Lexical fields are defined, as indicated above, by placing the letter 'L' immediately following the slant-bar (/) in <key_spec> definitions. Lexical sorting can be very useful when needed, but be aware that unnecessarily specifying lexical ordering may degrade performance of QSORT. --- Examples --- Produce a sorted directory listing and display it on the console a screen's worth at a time: A>DIR | QSORT | MORE This demonstrates the use of QSORT as a "filter" in a "pipe." Produce a directory listing sorted by creation date and time, and display it on the console a screen's worth at a time: A>DIR | QSORT /30:2 /24:5 /39 /34:5 | MORE The output of the DIR command is piped to QSORT. The key fields defined are, from left to right (major to minor), year (2 digits), month and day, AM/PM flag and time. The output of QSORT is then piped to MORE for display. Next, replace the unsorted FILE.TXT with the same data sorted in reverse order. Use columns 10 to 16 as the sort key: A>QSORT FILE.TXT /-10:7 or A>QSORT FILE.TXT /10:7 /R or (SORT compatible) A>QSORT FILE.TXT /R /+10 Next, perform a simple sort on a file with up to 240-byte records A>QSORT LARGE.REC /M240 or A>QSORT LARGE.REC Note that the "/M240" parameter is no longer needed, but will not hurt. GLOSS.TXT is an unsorted glossary of terms. The term being defined by each entry appears first, followed by several lines of definition. The entries are separated by empty lines. Produce GLOSS.SRT, a sorted version of the glossary: A>QSORT /T <GLOSS.TXT >GLOSS.SRT (with redirection) or A>QSORT /T GLOSS.TXT GLOSS.SRT (without redirection) A lawyer keeps a running log of his billable activities in TIME.LOG. The first line of each entry is "mm/dd/yy hh:mm account#." He always places a tilde (~) in the last line of each entry. He wishes to sort the log by account number, and by ascending date and time within each account: QSORT /16:7 /7:2 /1:5 /10:5 /T~ TIME.LOG The directory of users for a bulletin board system is kept in a binary file of fixed-length records 180 bytes long. The user name is a 26-character field beginning in the first position and the city/state field is a 16-character field beginning in the fortieth position. Sort the file by city/state and name. QSORT /F180 /40:16 /1:26 USER.BBS --- Implementation Notes --- QSORT is intended as an enhanced replacement for DOS SORT. It is nearly fully upward compatible, but provides much more flexibility. Multiple sort keys may be specified, a pseudo in-place sort may be performed and files and/or records of any size may be sorted provided only that there is sufficient disk space for work files and the output file. QSORT uses the "quick sort" algorithm, which cannot guarantee the order of records whose keys are all equal. This is the one "incompatibility" with DOS SORT, which retains the original order of records when its only key compares equal. This is important to SORT because it must be invoked multiple times to effect a multiple key sort. With QSORT, you only sort once and there are usually enough keys available to insure you get the order you want the first time. QSORT uses a sort buffer of about 50K bytes and will fill the buffer as full as possible, and then sort the contents of the buffer. If it has reached the end of the input file and has not yet generated any work files, the contents of the buffer are written to the output file, completing the sort operation. If the input file is too large to fit into the sort buffer, as much of the input file as possible is read into the buffer, sorted, then written to a temporary work file. This process is repeated as many times as necessary to process the entire input file, each time creating a new work file for the sorted output. Upon completion of the "sort phase," QSORT begins a "merge phase." Each work file is a sorted sub-set of the input file. Thus, work files may be read sequentially and combined to produce a sorted output. QSORT will open as many work files as DOS permits (more on this later). If all the remaining work files can be opened, the sorted result is written to the output file. Otherwise, a new work file is created and another merge pass will be required. On each merge pass, the number of work files is reduced and eventually all remaining work files will be opened and the sorted output file will be written completing the sort operation. QSORT is smart enough to never have just one work file remaining, which would require an unnecessary copy operation. In fact, QSORT is smarter than just that in its handling of the merge phase. If more than one merge pass is required, all the data merged during the first pass will have to be merged again, so QSORT attempts to minimize the first pass. For example, if QSORT discovers it may only open 15 files at a time, and there are 16 temporary files, it will only merge two files on the first pass, creating a 17th file as it does. Then in the second pass, it will merge all 15 remaining files to the output file. The less data it processes twice, the faster it performs the sort! With nothing else to guide it, QSORT places its temporary files in the default directory. Either of two "environment variables" can override this. (See your DOS manual for information on environment variables and the SET command.) The command: SET QSTMP=<path> or SET TMP=<path> will define a path for QSORT to use for its temporaries. QSORT first looks for the environment variable QSTMP. If it does not exist, QSORT next looks for TMP. TMP is a de facto standard used by many programs, and is usually defined in your AUTOEXEC.BAT batch file. You might have TMP specifying a 64K RAM disk to speed up your compiler. In this case, an attempt to sort a 100K file is doomed to failure. Rather than redefine TMP, you may define QSTMP to force QSORT to use some directory on your hard disk. In fact: SET QSTMP=. tells QSORT to always use the default directory anyway! QSORT, to work properly, needs enough space on the output disk to hold the output file. Even if the input file is to be deleted and resides in the same directory, that is not done until after the output file has been successfully written. If one merge pass is required, the disk QSORT uses for temporaries should have about 10% more space than the size of the input file for temporary merge files. If more than one merge pass will be required, allow about twice the size of the input file as temporary merge file space. One of the advantages of controlling where QSORT places its temporary files is to insure adequate space for them. A second is speed. If the temporary files can be placed on a separate disk from the input and output files, disk seeking is minimized and performance improved. Each time QSORT must create a new temporary merge file, the data put into it will be processed again. Obviously, the more files QSORT can open during the merge phase, the fewer times it will have to handle each record and the faster it can sort large files. If DOS is properly pre-conditioned, QSORT can have up to 15 temporary merge files open at once, and very large files can be sorted with just one sort pass and one merge pass. Unfortunately, that capability is not automatic. DOS has a fixed number of file "handles" that it associates with open files. The default number is eight, but DOS opens five of them for standard input, standard output, standard error, standard printer and standard auxiliary device. That leaves three for merging. A 250K input file would produce five temporary merge files and that would take three merge passes; merge two into one, leaving four; merge two into one leaving three; and finally merge three into the output file. In the process, QSORT must read and write about 80% of the file twice during the merge phase. Worse yet, since you need at least three handles for merging, if you have resident programs that have open files, you can't merge at all! DOS can be told to set aside more space for file handles. Each handle is only 39 bytes and it's memory very well spent. One process can have a maximum of 20 handles open at one time, but since resident processes may be using handles, I recommend 25 to 35. To do this, the root directory of the DISK OR DISKS YOU BOOT FROM must contain a file named CONFIG.SYS. If your boot disk(s) already contains a CONFIG.SYS, edit it, or if not, create it to contain the following line: FILES=25 (or more) While we're at it, let's add one more thing to CONFIG.SYS which will improve the performance of QSORT and many other programs as well. DOS provides, by default, two disk buffers. These are the buffers it uses to do its disk reads and writes. During the merge phase QSORT may have many files open at once, reading from them in more or less random order. DOS may have to read the same physical sector several times to get all its data. But DOS can remember what's in each buffer and where it came from, and will not re-read a sector it already has in a buffer. DOS needs 528 bytes for each buffer. I recommend 20 buffers to make QSORT perform well under the most adverse conditions. This will require an additional 9504 bytes or slightly more than 9K, again memory well spent, so we add to CONFIG.SYS the following line: BUFFERS=20 See your DOS manual for more information on CONFIG.SYS. I hope you find this program useful. Your comments and suggestions are welcome. My address is at the top of this file.